'''
https://leetcode.cn/problems/brace-expansion
'''


from typing import List


class Solution:
    def expand(self, s: str) -> List[str]:
        n = len(s)
        res = []
        path = []
        def f(i):
            if i == n:
                res.append(''.join(path))
                return
            if s[i] != '{':
                path.append(s[i])
                f(i+1)
                path.pop()
            else:
                start = i + 1
                end = start + 1
                while s[end] != '}':
                    end += 2
                for j in range(start, end, 2):
                    path.append(s[j])
                    f(end + 1)
                    path.pop()
        f(0)
        return sorted(res)

s = "{a,b}c{d,e}f"
print(Solution().expand(s))



